#include <iostream>

void Swap(int* x,int* y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}

void AdjustUp(int *a,int child)
{
    int parent=(child-1)/2;
    while(child>0)
    {
        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            child=parent;
            parent=(child-1)/2;
        }
        else
        {
            break;
        }
    }

}

void AdjustDown(int*a,int n,int parent)
{
    int child=2*parent+1;
    while(child<n)
    {
        if(child+1<n&&a[child]<a[child+1])
        {
            child++;
        }
        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int *a,int n)
{
    //向下调整建堆
    for(int i=(n-1-1)/2;i>=0;i--)
    {
        AdjustDown(a,n,i);
    }

    //拍升序，建大堆
    int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		end--;
	}


}

int main()
{
    int a[10]={5,3,6,9,7,1,0,2,4,10};
    HeapSort(a,10);
    for(int i=0;i<10;i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    return 0;
}